package com.ywk.base.dataStructure.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
//邻接矩阵（图结构）：（1）深度优先遍历（2）广度优先遍历
public class GraphDemo {
	private ArrayList<String> vertexts;
	private int[][] edges;
	private int numOfEdges;
	private boolean[] isVisited;
	
	public static void main(String[] args) {
//		String vertexs[]= {"A","B","C","D","E"};
		String vertexs[]= {"A","B","C","D","E","F","G","h"};
		GraphDemo graph=new GraphDemo(vertexs.length);
		for(String vertex:vertexs) {
			graph.insertVertex(vertex);
		}
		
//		graph.insertEdges(0, 1, 1);
//		graph.insertEdges(0, 2, 1);
//		graph.insertEdges(1, 2, 1);
//		graph.insertEdges(1, 3, 1);
//		graph.insertEdges(1, 4, 1);
		
		graph.insertEdges(0, 1, 1);
		graph.insertEdges(0, 2, 1);
		graph.insertEdges(1, 3, 1);
		graph.insertEdges(1, 4, 1);
		graph.insertEdges(3, 5, 1);
		graph.insertEdges(4, 5, 1);
		graph.insertEdges(2, 6, 1);
		graph.insertEdges(2, 7, 1);
		graph.insertEdges(6, 7, 1);
		
		graph.show();
//		graph.dfs(0);
		System.out.println();
		graph.bfs(0);
	}
	
	public GraphDemo(int n) {
		edges=new int[n][n];
		vertexts=new ArrayList<String>(n);
		isVisited=new boolean[n];
	}
	
	//添加节点
	public void insertVertex(String vertex) {
		vertexts.add(vertex);
	}
	
	//添加两个节点间的边
	public void insertEdges(int v1,int v2,int weight) {
		edges[v1][v2]=weight;
		edges[v2][v1]=weight;
		numOfEdges++;
	}
	
	//显示图对应的矩阵
	public void show() {
//		for(int[] line:edges) {
//			for(int row:line) {
//				System.out.print(line[row]);
//			}
//			System.out.println();
//		}
		for(int[] line:edges) {
			System.out.println(Arrays.toString(line));
		}
	}
	
	//返回节点总个数
	public int numOfVertexs() {
		return vertexts.size();
	}
	
	//返回边数
	public int numOfEdges() {
		return numOfEdges;
	}
	
	//返回节点i（下标）对应的数据
	public String getValueByIndex(int index) {
		return vertexts.get(index);
	}
	
	//返回V1,V2的权值
	public int getWeight(int v1,int v2) {
		return edges[v1][v2];
	}
	
	//图的深度优先遍历
	public void dfs(int index) {
		System.out.print(getValueByIndex(index)+"->");
		isVisited[index]=true;
		for(int i=0;i<vertexts.size();i++) {
			if(edges[index][i]==1&&!isVisited[i]) {
				dfs(i);
			}else {
				continue;
			}
		}
	}
	
	//图的广度优先遍历
	public void bfs(int index) {
		Queue<Integer> q=new LinkedList<>();
		q.offer(index);
		isVisited[index]=true;
		while(q.size()>0) {
			for(int i=0;i<vertexts.size();i++) {
				if(!isVisited[i]&&edges[q.peek()][i]==1) {
					q.offer(i);
					isVisited[i]=true;
				}else {
					continue;
				}
			}
			System.out.print(getValueByIndex(q.poll())+"->");
		}
	}
}
